Arnhem Land đã là nơi sinh sống của thổ dân từ hàng chục nghìn năm và là nơi phát hiện ra chiếc rìu đá cổ nhất, được vài học giả ước tính là tới 35.500 năm tuổi.[3] Bán đảo Gove là một phòng tuyến quân sự của Úc vào chiến tranh thế giới II.

Từ ít nhất thế kỷ 18 (và có thể sớm hơn), những thương gia Hồi giáo từ Makassar (nay Indonesia) đã đến Arnhem Land để trao đổi, mua bán, và thu gom hải sâm (trepang).

Sự tiếp xúc với người Makassar này là ví dụ đầu tiên về sự gặp gỡ giữa thổ dân Úc và cư dân châu Á lân cận.[4]

Người Makassar trao đổi hàng hóa như quần áo, thuốc lá, dao, gạo, và rượu để lấy quyền đánh bắt trepang và thuê mướn lao động địa phương. Ngôn ngữ pidgin Makassar trở thành một lingua franca dọc theo duyên hải phía bắc.[4]